/*
 * @lc app=leetcode.cn id=141 lang=swift
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
/**
 * 采用快慢指针，快指针每走一步，都会拉开慢指针一个距离。最终一定会赶上。
 */
class Solution141 {
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        while fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast && fast != nil{
                return true
            }
        }
        return false
    }
   
   
    static func test()  {
        var head:ListNode?
        var tail:ListNode?
        for i in 1...4 {
            let node = ListNode(i)
            if i == 1 {
                head = node
                tail = head
            }else {
                tail?.next = node
                node.next = nil
                tail = node
            }
        }
        let has = Solution141().hasCycle(head)
        if  has {
            print("有环")
        }else {
            print("无环")
        }
    }
}
// @lc code=end

